package fireway;

/**
 * 最大公约数的递归示例
 *
 * @author fireway
 */
public class Gcd {
    private static final boolean DEBUG = false;

    /**
     * 辗转相除法
     *
     * 1) 若a可以整除b，则最大公约数是b
     * 2) 如果1不成立，最大公约数便是b与a%b的最大公约数
     * 示例：求(140,21)
     * 140%21 = 14
     * 21%14 = 7
     * 14%7 = 0
     * 返回7
     */
    public int divisor1(int m,int n) {
        // 保证参数m永远大于等于参数n
        if (m < n) {
            int temp = m;
            m = n;
            n = temp;
        }

        if (DEBUG) System.out.println("Entering m[" + m + "], n[" + n + "]");

        if (m % n == 0) {
            if (DEBUG) System.out.println("Returning " + n);
            return n;
        } else {
            int temp = divisor1(n, m % n);
            if (DEBUG) System.out.println("Returning " + temp);
            return temp;
        }
    }

    /**
     * 更相减损法
     *
     * 取两个数中的最大的数做减数，较小的数做被减数，用最大的数减去小的数，如果结果为0，则被减数就是这两个数的最大公约数，
     * 如果结果不为0，则继续用这两个数中最大的数减较小的数，直到结果为0，则最大公约数为被减数。
     */
    public int divisor2(int m,int n) {
        // 保证参数m永远大于等于参数n
        if (m < n) {
            int temp = m;
            m = n;
            n = temp;
        }

        if (DEBUG) System.out.println("Entering m[" + m + "], n[" + n + "]");

        if (m == n) {
            if (DEBUG) System.out.println("Returning " + m);
            return m;
        } else {
            int temp = divisor2(n, m - n);
            if (DEBUG) System.out.println("Returning " + temp);
            return temp;
        }
    }

    /**
     * 穷举法
     * 这个整数 i从2开始循环累加，一直累加到m和 n中较小参数的一半为止。
     * 循环结束后，上一次寻找到的能够被两数整除的最大 i值，就是两数的最大公约数。
     */
    public int divisor3(int m,int n) {
        // 保证参数m永远大于等于参数n
        if (m < n) {
            int temp = m;
            m = n;
            n = temp;
        }

        int nRet = 1;
        for (int i = 2; i < n / 2; i++) {
            if (m % i == 0 && n % i == 0) {
                nRet = i;
            }
        }
        return nRet;
    }
}
